class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if(n == 1) return {0};
        vector<int> ret;
        vector<int> deg(n);
        vector<unordered_set<int> > edgess(n);
        for(auto& vc : edges){
            edgess[vc[0]].insert(vc[1]);
            edgess[vc[1]].insert(vc[0]);
            deg[vc[1]]++;
            deg[vc[0]]++;
        }
        queue<int> qe;
        for(int i = 0;i < n;i++){
            if(deg[i] == 1){
                qe.push(i);
            }
        }
        
        while(!qe.empty()){
            ret.clear();
            int size = qe.size();
            for(int i = 0;i < size;i++){
                int x = qe.front();
                qe.pop();
                ret.push_back(x);
                for(const int& e : edgess[x]){
                    deg[e]--;
                    if(deg[e] == 1){
                        qe.push(e);
                    }
                }
            }
        }
        return ret;
    }
};
